package com.zp.self.module.level_4_算法练习.算法.动态规划;

import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_97_交错字符串 {
    @Test
    public void main() {
        System.out.println(isInterleave("aabcc","dbbca","aadbbcbcac"));
    }

    /**
    题目：给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
     两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

     s = s1 + s2 + ... + sn
     t = t1 + t2 + ... + tm
     |n - m| <= 1
     交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
     注意：a + b 意味着字符串 a 和 b 连接。

    分析：【P 💜💜💜💜】
       1.动态规划：状态方程按情况分析
                元素定义：dp[x][y]表示当s1出x个字符，s2出y个字符 是否能够得出s3
                状态方程：dp[x][y] ： dp[x-1][y] ==true 时 比较s1、s3  .   dp[x][y-1] ==true 比较s2、s3
                初始值： dp[x][0]  :s1.sbuString(0,x) == s3.sbuString(0,x) ,即：判断s1、s2能否与s3相同

    边界值 & 注意点：
       1.
     **/
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1=s1.length(),length2=s2.length(),length3=s3.length();
        if(length1+length2!=length3) return false;
        char[] chars1 = s1.toCharArray(),chars2 = s2.toCharArray(),chars3 = s3.toCharArray();

        boolean[][] dp = new boolean[length1+1][length2+1];
        for (int x = 1; x <= length1; x++) {//初始化 列
           if(chars1[x-1] ==chars3[x-1])
               dp[x][0] = true;
           else break;
        }
        for (int y = 1; y <= length2; y++) {//初始化 行
            if(chars2[y-1] ==chars3[y-1])
                dp[0][y] = true;
            else break;
        }
        for (int x = 1; x <= length1; x++) {
            for (int y = 1; y <= length2; y++) {
                if(dp[x-1][y])
                    dp [x][y] = chars1[x-1]==chars3[x+y-1] ;
                if(dp[x][y-1] && !dp [x][y])
                    dp [x][y] = chars2[y-1]==chars3[x+y-1];
            }
        }
        return dp[length1][length2] || length3==0;
    }
}
